package net.cloudsun.tree.rb;

import net.cloudsun.tree.binary.BinaryNode;
import net.cloudsun.tree.orderbinary.OrderBinaryNode;

/**
 * @author Ryan
 * @since
 */
public class RBNode<T extends Comparable<T>> extends OrderBinaryNode<T> {
    public static final boolean RED = true;
    public static final boolean BLACK = !RED;
    private boolean color;

    public RBNode(T t) {
        super(t);
        color = RED;
    }

    @Override
    public void add(BinaryNode<T> newNode) {
        super.add(newNode);
        // fix-up算法
        RBNode<T> current = (RBNode<T>) newNode;
        current.fixup();
    }

    /**
     * 修正
     */
    public void fixup() {
        final RBNode<T> root = (RBNode<T>) getRoot();
        RBNode<T> current = this;
        while (current != root && current.parent != null && current.getParent().color == RED) {
            // 如果parent是左孩子
            if (current.parent.isLeftChild()) {
                current = parentIsLeft(current);
            } else {
                current = parentIsRight(current);
            }
        }
    }

    public void fixupAfterDeletion() {
        if (this.color == RED) {
            return;
        }
        RBNode<T> root = (RBNode<T>) this.getRoot();
        // 如果删除的是黑节点
        // case 1 兄弟是红色
        RBNode<T> current = this;
        while (current != root && current.color == BLACK) {
            final RBNode<T> sibling = (RBNode<T>) current.getSibling();
            if (sibling != null && colorOf(sibling) == RED) {
                siblingIsRed(current, sibling);
            } else {
                current = siblingIsBlack(root, current, sibling);
            }
        }
        current.color = BLACK;
    }

    private RBNode<T> siblingIsBlack(RBNode<T> root, RBNode<T> current, RBNode<T> sibling) {
        if (sibling != null && colorOf(sibling.getLeft()) == RED) {
            // 这里又分两种情况
            if (current.isLeftChild()) {
                // 兄弟变红 兄弟黑色高度-1

                sibling.setColor(RED);
                //
                // 兄弟左子变黑 兄弟左子黑色高度 + 1
                sibling.getLeft().setColor(BLACK);

                // 右旋
                sibling.rightRotate();
            } else {

                sibling.getLeft().setColor(BLACK);
                sibling.setColor(current.getParent().color);
                current.getParent().setColor(BLACK);

                current.getParent().rightRotate();
                current = root;
            }

        } else if (sibling != null && colorOf(sibling.getRight()) == RED) {
            //
            // 兄弟是黑的
            // 分三种场景
            // 1 兄弟有红色孩子
            // 1 兄弟没有红色孩子
            // 因为为了保持黑色高度一致，所以一个节点仅有一个孩子时，不能只有一个黑色孩子。
            if (current.isLeftChild()) {

                sibling.getRight().setColor(BLACK);
                sibling.setColor(current.getParent().color);
                current.getParent().setColor(BLACK);

                current.getParent().leftRotate();

                current = root;

            } else {
                // 自己是哥哥，大侄子红色

                // 兄弟变红 兄弟黑色高度-1
                sibling.setColor(RED);
                //
                // 兄弟左子变黑 兄弟左子黑色高度 + 1
                sibling.getRight().setColor(BLACK);

                // 左旋
                sibling.leftRotate();
            }
        } else {
            setColor(sibling, RED);
            current = current.getParent();
        }
        return current;
    }

    private void siblingIsRed(RBNode<T> current, RBNode<T> sibling) {
        // 整体黑色高度需要-1
        // 兄弟为黑，parent为红，黑色高度不变

        sibling.color = BLACK;
        current.getParent().color = RED;

        // 左旋
        if (current.isLeftChild()) {

            sibling.getParent().leftRotate();
        } else {
            sibling.getParent().rightRotate();
        }
    }

    private static boolean colorOf(RBNode node) {
        return node == null ? BLACK : node.color;
    }



    /**
     * ll or lr
     * @param current
     * @return
     */
    private RBNode<T> parentIsLeft(RBNode<T> current) {
        RBNode<T> grandparent = current.getParent().getParent();
        RBNode<T> uncle = grandparent.getRight();
        // 红黑树 case 1 叔叔是红色 ll red or lr red
        if (uncle != null && uncle.color == RED) {

            // case 1的处理有点坑人
            current.getParent().color = BLACK;
            uncle.setColor(BLACK);
            grandparent.color = RED;
            current = grandparent;

        } else {
            // lr
            if (current.isRightChild()) {
                /*
                 * case 2 叔叔是黑色当前节点是右孩子
                 * 97B
                 *┌┘
                 *68R
                 *└┐
                 * 84R
                 *左旋
                 *  97B
                 * ┌┘
                 * 84R
                 *┌┘
                 *68R
                 * 这就变成了第一种情况了
                 */
                current.getParent().leftRotate();

            } else {
                // ll
                // case 3 叔叔是黑色，当前节点是左孩子,LL
                // 祖父设置为红色
                current.getParent().setColor(BLACK);
                grandparent.color = RED;
                grandparent.rightRotate();
            }
        }
        return current;
    }

    /**
     * rr or rl
     * @param current
     * @return
     */
    private RBNode<T> parentIsRight(RBNode<T> current) {
        RBNode<T> grandparent = current.getParent().getParent();
        RBNode<T> uncle = grandparent == null ? null : grandparent.getLeft();
        // 红黑树 case 1 叔叔是红色
        if (uncle != null && uncle.color == RED) {

            current.getParent().color = BLACK;
            uncle.setColor(BLACK);
            grandparent.color = RED;
            current = grandparent;

        } else {
            // 叔叔是黑色
            // 这里是很容易空指针异常得
            // rr 型
            if (current.isRightChild()) {
                // case 2 叔叔是黑色当前节点是右孩子
                // 父节点为当前节点
                current = current.getParent();
                current.setColor(BLACK);
                setColor(grandparent, RED);
                // 左旋
                if (grandparent != null) {
                    grandparent.leftRotate();
                }
            } else {
                // case 3 叔叔是黑色，rl型，右旋为rr型
                current.getParent().rightRotate();
            }
        }
        return current;
    }

    private static <T> void setColor(BinaryNode<T> node, boolean color) {
        if (node != null) {
            ((RBNode) node).setColor(color);
        }
    }

    @Override
    protected void rightRotate() {
        // 右旋颜色也需要变化
        final RBNode<T> originalLeft = getLeft();
        final boolean newThisColor = originalLeft == null ? BLACK : originalLeft.color;
        final boolean originalColor = this.color;
        super.rightRotate();
        this.setColor(newThisColor);
        if (originalLeft != null) {
            originalLeft.setColor(originalColor);
        }
    }

    @Override
    protected void leftRotate() {
        // 右旋颜色也需要变化
        final RBNode<T> originalRight = getRight();
        final boolean newThisColor = originalRight == null ? BLACK : originalRight.color;
        final boolean originalColor = this.color;
        super.leftRotate();
        this.setColor(newThisColor);
        if (originalRight != null) {
            originalRight.setColor(originalColor);
        }
    }

    @Override
    public RBNode<T> getRight() {
        return (RBNode<T>) super.getRight();
    }

    @Override
    public RBNode<T> getLeft() {
        return (RBNode<T>) super.getLeft();
    }

    @Override
    public RBNode<T> getParent() {
        return (RBNode<T>) super.getParent();
    }

    @Override
    public String toString() {
        if (color == RED) {
            return value + "R";
        }
        return value + "B";
    }

    public void setColor(boolean color) {
        this.color = color;
    }

    public boolean getColor() {
        return color;
    }
}
